package algorithm.array;

import algorithm.array.model.Interval;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode : https://leetcode.com/problems/merge-intervals/description/
 * Difficulty : Medium
 *
 * 合并区间对象,由于interval 不会保证正序，所以一般情况的正序排列处理不正确
 * 举栗：
 * Input:  [[1,3],[2,6],[8,10],[15,18]]
 * Output: [[1,6],[8,10],[15,18]]
 *
 * Input:  [[1,4],[0,4]]
 * Output: [[0,4]]
 * @Author Antony
 * @Since 2018/7/25 16:45
 */
public class MergeIntervals {


    /**
     * beats 93.40% - 13ms
     * 时间复杂度：O(NlogN)
     *
     * 把start和end单独提取出来，然后排序
     * 按规指定规则结合start和end 为interval 然后加到结果中
     *
     * 参考思路：
     * https://leetcode.com/problems/merge-intervals/discuss/21223/Beat-98-Java.-Sort-start-and-end-respectively.
     *
     */
    public List<Interval> merge(List<Interval> intervals) {
        int size = intervals.size();
        List<Interval> res = new ArrayList<>();
        int[] start = new int[size];
        int[] end = new int[size];
        int index=0;
        for(Interval inter : intervals){
            start[index] = inter.start;
            end[index] = inter.end;
            index++;
        }

        Arrays.sort(start);
        Arrays.sort(end);
        // i逐个往后走，指向的是end的指针
        // j保存start的指针，当满足条件时构造interval，然后更新指针为i+1
        for(int i=0,j=0; i<size; i++){
            if(i==size-1 || start[i+1] > end[i]){
                res.add(new Interval(start[j], end[i]));
                j = i+1;
            }
        }

        return res;
    }

    public List<Interval> merge_wrong(List<Interval> intervals) {
        if(intervals == null) return null;
        List<Interval> result = new ArrayList<>();
        Interval curr = null;
        for(Interval inter : intervals){
            if(curr == null){
                curr = inter;
            }
            if(inter.start <= curr.end){
                curr.end = inter.end;
            }else{
                result.add(curr);
                curr = inter;
            }
        }
        if(curr != null) result.add(curr);

        return result;
    }
}
